#include <stdlib.h>
#include <stdio.h>

typedef char DataType;
typedef struct Node
{
    DataType data;/*数据域*/
    struct Node *leftChild;/*左子树指针*/
    struct Node *rightChild;/*右子树指针*/
} BiTreeNode;/*结点的结构体定义*/

// 根据带有显式空子节点的先序序列，构建二叉树，将其根节点的地址存入 *root_pp 中
// 初始传入的root_pp的值无任何意义（也即root_pp尚未被正确地初始化，因此需要你来初始化）
// pre_order_seq 指向的字符串类似 "ABC##DE#G##F###"，其中 # 表示显式的空子节点（空指针域），
// 这一类空子节点并不需要被创建对应的struct Node或者BiTreeNode
void create_tree(BiTreeNode ** root_pp, char * pre_order_seq, int num_elements) {

    *root_pp = (BiTreeNode *) malloc(sizeof(BiTreeNode));
    static int num_element = -1;
    num_element++;
    if (pre_order_seq[num_element] != '\0' && pre_order_seq[num_element] != '#') {
        (*root_pp) = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        (*root_pp)->data = pre_order_seq[num_element];
        create_tree(&((*root_pp)->leftChild), pre_order_seq, num_elements);
        create_tree(&((*root_pp)->rightChild), pre_order_seq, num_elements);
    }
    else {
        (*root_pp) = 0;
    }
}

//使用visit(item)函数前序遍历二叉树t
void pre_order_traverse(BiTreeNode *t, void visit(DataType item)){
    if(t != NULL){
        visit(t->data);
        pre_order_traverse(t->leftChild,visit);
        pre_order_traverse(t->rightChild,visit);
    }
}

//使用visit(item)函数中序遍历二叉树t
void in_order_traverse(BiTreeNode *t, void visit(DataType item)){
    if(t != NULL){
        in_order_traverse(t->leftChild, visit);
        visit(t->data);
        in_order_traverse(t->rightChild, visit);
    }
}

//使用void visit(DateType item)函数后序遍历二叉树t
void post_order_traverse(BiTreeNode *t, void visit(DataType item)){
    if (t != NULL) {
        post_order_traverse(t->leftChild, visit);
        post_order_traverse(t->rightChild, visit);
        visit(t->data);
    }
}

// 可以无需更改本函数的实现
void visit(DataType item){
    printf("%c ", item);
}

// 查找元素值x是否在二叉树中
// 如果找到，返回值为x的结点的指针，否则返回NULL
BiTreeNode * search(BiTreeNode *root, DataType x)
{
    BiTreeNode *find = NULL;
    if (root != NULL) {
        if (root->data == x) {
            find = root;
        } else {
            //从左右子树中查找，并返回给find
            find = search(root->rightChild, x);
            //如果为空，则是在相应的左右子树中没有找到
            if (find == NULL) {
                //从左右子树中查找，并返回给find
                find = search(root->leftChild, x);
            }
        }
    }
    return find;
}
// 递归地销毁由 *root 所指向根节点的树：释放该树涉及的所有动态分配的内存空间
void destroy(BiTreeNode **root){
    if ((*root) != NULL && (*root)->leftChild != NULL)
        destroy(&(*root)->leftChild);

    if ((*root) != NULL && (*root)->rightChild != NULL)
        destroy(&(*root)->rightChild);

    free(*root);
}
void main(void) {
    BiTreeNode *root, *find;

    char *pre_order_seq = "ABC##DE#G##F###";
    create_tree(&root, pre_order_seq, 15);
    pre_order_traverse(root, visit);
    printf("\n");
    // 输出应该为 A B C D E G F
    in_order_traverse(root, visit);
    printf("\n");
    // 输出应该为 C B E G D F A
    post_order_traverse(root, visit);
    // 输出应该为 C G E F D B A
    char x = 'E';
    find = search(root, x);
    if (find != NULL)
        printf("\n Data element '%c' in binary tree \n", x);
    else
        printf("\n Data element '%c' is not in a binary tree \n", x);
    x = 'H';
    find = search(root, x);
    if (find != NULL)
        printf("\n Data element '%c' in binary tree \n", x);
    else
        printf("\n Data element '%c' is not in a binary tree \n", x);
    destroy(&root);
}
//ceshi